// 40 组合总和 II
// https://leetcode.cn/problems/combination-sum-ii/description/
/**
 * 
示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

 */

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function (candidates, target) {
    //
    let hash = hashMap(candidates);
    console.log(`[combinationSum2] candidates to hash:`);
    console.log(JSON.stringify(hash));
    // return;

    // 本题应该使用回溯算法
    let res = backTracking(hash, [], target, []);

    if (res.length === 0) {
        console.log(
            `[combinationSum2] NO answer for candidates ${JSON.stringify(
                candidates
            )} and target ${target}`
        );
    } else {
        console.log(
            `[combinationSum2] ${
                res.length
            } answers for candidates ${JSON.stringify(
                candidates
            )} and target ${target}`
        );

        console.log(`output >> ${JSON.stringify(res)}`);
    }

    return res;
};

var hashMap = function (arr) {
    let res = {};

    for (let ele of arr) {
        if (res[ele] > 0) res[ele] += 1;
        else res[ele] = 1;
    }

    let ret = [];

    Object.keys(res).forEach((key) => {
        ret.push([parseInt(key), parseInt(res[key])]);
    });

    return ret;
};

var backTracking = function (
    remainInCandidates,
    curArr,
    target,
    finalCollector
) {
    if (remainInCandidates.length === 0) {
        return;
    }

    for (let i = 0; i < remainInCandidates.length; i++) {
        for (let j = 1; j <= remainInCandidates[i][1]; j++) {
            let curVal = j * remainInCandidates[i][0]; // 使用j个数字，代表取当前j个相同数字的总和
            if (curVal > target) break;

            curArr.push(...new Array(j).fill(remainInCandidates[i][0]));
            const newTarget = target - curVal;

            if (newTarget === 0) {
                finalCollector.push([].concat(curArr));
                console.log(`[backtracking] find answer`);
            } else if (newTarget > 0) {
                backTracking(
                    remainInCandidates.slice(i + 1),
                    [].concat(curArr),
                    newTarget,
                    finalCollector
                );
            }

            curArr.splice(curArr.length - j, j);
        }
    }

    return finalCollector;
};

var strLongArr = function (arr) {
    let str = JSON.stringify(arr);
    if (str.length >= 18) {
        str = str.substring(0, 7) + '...' + str.substring(str.length - 8);
    }

    return str;
};

combinationSum2([1, 2], 3); // [[1,2]]
combinationSum2([1, 2], 0); // null
combinationSum2([1], 3); // null
combinationSum2([2, 3, 6, 7], 7); // [[7]]
combinationSum2([2, 3, 5], 8); // [[3,5]]
combinationSum2([8, 7, 4, 3], 11); // [[3,8],[4,7]]
combinationSum2([4, 2, 8], 8); // [[8]]
combinationSum2([10, 1, 2, 7, 6, 1, 5], 8); // [[1,2,5],[1,7],[1,1,6],[2,6]]
combinationSum2([2, 5, 2, 1, 2], 5); // [[1,2,2],[5]]
combinationSum2(
    [
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
        1, 1, 1, 1, 2,
    ],
    30
); // [[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]]
combinationSum2(
    [
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
        1, 1, 1, 1, 1, 1,
    ],
    30
); // [[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]]s
